package LinkList;

/*
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/fnzd1/
 */

public class _51合并两个有序链表 {
    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //迭代
    //双指针 + 一次遍历 + 判断、
    //时间O(n)  空间O(1)
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }

        ListNode dummyhead = new ListNode(0,list2);
        ListNode curr2 = dummyhead;
        ListNode curr1 = list1;
        while (curr1 != null){
            int nextVal;
            if(curr2.next == null){
                nextVal = Integer.MAX_VALUE;
            }else {
                nextVal = curr2.next.val;
            }
            ListNode next1 = curr1.next;
            if(nextVal > curr1.val){
                ListNode next2 = curr2.next;
                curr2.next = curr1;
                curr1.next = next2;
                curr2 = curr2.next;
            }else {
                while (nextVal <= curr1.val){
                    curr2 = curr2.next;
                    if(curr2.next == null){
                        curr2.next = curr1;
                        return dummyhead.next;
                    }else {
                        nextVal = curr2.next.val;
                    }
                }
                ListNode next2 = curr2.next;
                curr2.next = curr1;
                curr1.next = next2;
                curr2 = curr2.next;
            }

            curr1 = next1;
        }
        return dummyhead.next;

    }

    //官解:迭代
//        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//            ListNode prehead = new ListNode(-1);
//
//            ListNode prev = prehead;
//            while (l1 != null && l2 != null) {
//                if (l1.val <= l2.val) {
//                    prev.next = l1;
//                    l1 = l1.next;
//                } else {
//                    prev.next = l2;
//                    l2 = l2.next;
//                }
//                prev = prev.next;
//            }
//
//            // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
//            prev.next = l1 == null ? l2 : l1;
//
//            return prehead.next;
//        }

    

}
